package dp.bag_problem;

import org.junit.Test;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-09-03 15:27
 */
public class T416_canPartition {
    @Test
    public void test() {
        canPartition(new int[]{1, 5, 11, 5});
    }
    // 要满足分割之后，两个子数组的和刚好相等
    // 既然总价值是固定的，可以转成01背包问题
    // 说明各自的和为 sum/2
    // 这里nums数组的值既是背包容量，也是背包的价值，
    // 如果满足背包容量恰好等于背包价值，说明满足分割等和数组
    //
    // 定义: dp[i][j] ，boolean 表示 存放[0...i]任意个物品，容量为j，且价值为j的条件是否成立
    // 递推式：(or关系)
    // 1) dp[i][j] = dp[i-1][j]
    // 2) dp[i][j] = true (nums[i] == j)
    // 3) dp[i][j] = dp[i-1][j-nums[i]]
    // 初始化：dp[i][0] = false、dp[0][nums[0]] = true(nums[0]<=target)、dp[0][j] = false
    // 返回值: dp[nums.length-1][target]
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];
        if (sum % 2 != 0) return false;
        int target = sum / 2;

        boolean[][] dp = new boolean[nums.length][target + 1];

        // 当i为0 的时候，只有容量为nums[0]的时候才为true
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }

        // i从1开始
        for (int i = 1; i < nums.length; i++) {
            // for(int j = nums[i];j <= target;j++){
            for (int j = 1; j <= target; j++) {
                dp[i][j] = dp[i - 1][j];
                if (nums[i] == j) {
                    dp[i][j] = true;
                    continue;
                }
                if (nums[i] < j) {
                    // 这里不能直接写 dp[i][j] =  dp[i-1][j-nums[j]]; 不然如果
                    // 原先dp[i][j] = true,而 dp[i-1][j-nums[j]]为false，就会被覆盖掉
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }


        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();;
        }

        // false true false false false false false false false false false false
        // false true false false false true true false false false false false
        // false true false false false true true false false false false true
        // false true false false false true true false false false true true
        return dp[nums.length - 1][target];
    }
}
